package com.mathdroid.model.abilities.optimizer;

import java.awt.Toolkit;
import java.util.LinkedList;
import java.util.concurrent.ExecutionException;

import javax.swing.SwingWorker;

import com.mathdroid.model.Model;
import com.mathdroid.model.abilities.Ability;
import com.mathdroid.model.abilities.AbilityTemplate;

/**
 * This optimizer searches for the best priorities of abilities. This task
 * is delegated and split to multiple threads.
 */
public final class AbilityOptimizer 
extends SwingWorker<AbilityOptimizerResultList, Void> {
	
	/**
	 * The best results that were reached.
	 */
	private AbilityOptimizerResultList results = 
		new AbilityOptimizerResultList();
	
	/**
	 * The amount of physical system cores.
	 */
	private final int cores = Runtime.getRuntime().availableProcessors();
	
	/**
	 * A list of delegated tasks.
	 */
	private final LinkedList<AbilityOptimizerDelegate> delegates = 
		new LinkedList<AbilityOptimizerDelegate>();
	
	/**
	 * Temporarily contains not optimizable abilities.
	 */
	private AbilityTemplate unoptimizableAbilities = null;

	/**
	 * Get the optimal priorities. The algorithm generates all possible
	 * combinations of priorities. See http://en.wikipedia.org/wiki/Permutation
	 * "Generation in lexicographic order" for more information. After 
	 * generating each combination the combination has to be simulated.
	 * 
	 * @return The best results in a list.
	 */
	public AbilityOptimizerResultList getOptimalPriorities() {
		AbilityTemplate list = Model.getProfile().getAbilities();	
		
		/* Remove not optimizable abilities */
		list = this.prepare(list);
		
		final int size = list.size();	
		final int[] a = this.buildPermutationList(size);
		final double mutations = this.faculty(size);
		double loop = 0;
		boolean indexFound = true;
		int k = 0;
		int l = 0;
		int tempValue = 0;
		int ri = 0;
		int rj = 0;
		int percent = 0;
		int lastpercent = 0;
		
		/*
		 * Create the delegates and start them.
		 */
		for (int i = 0; i < cores; i++) {
			this.delegates.add(new AbilityOptimizerDelegate());
			this.delegates.get(i).execute();
		}
		
		/*
		 * Delegate the initial permutation (0, 1, ... , n).
		 */
		this.delegate(loop, a, list);
		loop++;
		
		/*
		 * Repeat the loop until no index is found that satisfies
		 * a[k] < a[k + 1].
		 */
		while (indexFound && !this.isCancelled()) {
			indexFound = false;
			
			/*
			 * Find the highest index k that satisfies a[k] < a[k + 1]. So lets
			 * go from the highest to the lowest index and start at (size - 2).
			 */
			for (k = size - 2; k >= 0; k--) {
				if (a[k] < a[k + 1]) {
					indexFound = true;
					break;
				}
			}
			
			/*
			 * If there is such an index continue.
			 */
			if (indexFound) {
				
				/* 
				 * Find the largest index l, that satisfies a[l] > a[k]. The
				 * lowest possible index l is the index k + 1, because of the
				 * step before.
				 */
				for (l = size - 1; l > 0; l--) {
					if (a[l] > a[k]) {
						break;
					}
				}
				
				/* Swap */
				tempValue = a[k];
				a[k] = a[l];
				a[l] = tempValue;
				
				/* Reverse the sequence k + 1 up to size - 1. Lets swap pairs
				 * of the first and last index of the sequence. If the 
				 * sequence has an odd number of elements the center element
				 * is swapped with itself.
				 */
				ri = k + 1;
				rj = size - 1;
				
				while (ri <= rj) {
					/* Swap */
					tempValue = a[ri];
					a[ri] = a[rj];
					a[rj] = tempValue;
					
					ri++;
					rj--;
				}
				
				/*
				 * Delegate this new permutation. 
				 */
				this.delegate(loop, a, list);

				/*
				 * Update the progress bar.
				 */
				loop++;
				percent = (int) (loop * 100.0 / mutations);
				
				if (percent != lastpercent) {
					lastpercent = percent;
					this.setProgress(percent);
				}
			}
		}
		
		/* Notify the tasks that the queue will no longer be filled. */
		for (int i = 0; i < this.cores; i++) {
			this.delegates.get(i).finishIt();
		}
		
		/* Wait for the tasks and combine the results. */
		for (int i = 0; i < this.cores; i++) {
			try {
				for (AbilityOptimizerResult r : this.delegates.get(i).get()) {
					this.results.offer(r);
				}
			} catch (InterruptedException e) {
				e.printStackTrace();
			} catch (ExecutionException e) {
				e.printStackTrace();
			}
		}
		
		this.restoreUnoptimizedAbilities();
		
		return this.results;
	}
	
	/**
	 * Restore the abilities that were not optimizable.
	 */
	private void restoreUnoptimizedAbilities() {
		for (AbilityOptimizerResult aor : this.results) {
			for (Ability a : this.unoptimizableAbilities) {
				aor.getPrio().add(a);
			}
		}
	}

	/**
	 * Remove not optimizable abilities from the list.
	 * @param l Complete ability list.
	 * @return Prepared list.
	 */
	private AbilityTemplate prepare(final AbilityTemplate l) {
		final AbilityTemplate list = new AbilityTemplate();
		this.unoptimizableAbilities = new AbilityTemplate();
		
		for (Ability a : l) {
			/* 
			 * The ability has to be ...
			 * - Available because of talents
			 * - Enabled by the user
			 * - Optimizable
			 */
			if (a.isAvailabe() && a.isEnabled() && a.isUsedForOptimization()) {
				list.add(a);
			} else {
				/* 
				 * Remember the removed abilities and add them later to
				 * the end of the list.
				 */
				this.unoptimizableAbilities.add(a);
			}
		}
		
		return list;
	}

	/**
	 * Add the permutation to a queue.
	 * @param i Permutation number.
	 * @param a The permutation sequence.
	 * @param list The ability list.
	 */
	private void delegate(
			final double i, final int[] a, final AbilityTemplate list) {
		boolean timeout = true;
		
		while (timeout) {
			timeout = !this.delegates.get((int) (i % this.cores))
			.queue(this.mapPriorityList(a, list));
		}
	}

	/**
	 * Calculate the faculty of the integer value.
	 * @param i Integer value.
	 * @return Faculty.
	 */
	private double faculty(final int i) {
		double result = 1;
		
		for (int j = i; j > 1; j--) {
			result *= j;
		}
		
		return result;
	}
	
	/**
	 * Map an combination to a new ability priority list. For example:
	 * The first index in the array is 5. So index 5 of the ability list
	 * is put on index 0 in the new list, because the fifth index has the
	 * highest priority in the combination.
	 * 
	 * @param p The combination to map.
	 * @param list The original list to map from. This list never changes.
	 * @return A unique combination of priorities.
	 */
	private AbilityTemplate mapPriorityList(
			final int[] p, 
			final AbilityTemplate list) {
		
		final AbilityTemplate a = new AbilityTemplate();
		
		for (int i : p) {
			a.add(list.get(i));
		}
		
		return a;
	}

	/**
	 * Creates an integer array of the given size. Each element is 
	 * initialized with the index value.
	 * 
	 * @param size Size of the array.
	 * @return A new integer array.
	 */
	private int[] buildPermutationList(final int size) {
		int[] a = new int[size];
		
		for (int i = 0; i < size; i++) {
			a[i] = i;
		}
		
		return a;
	}

	@Override
	protected AbilityOptimizerResultList doInBackground() throws Exception {
		return this.getOptimalPriorities();
	}
	
	@Override
	public void done() {
		Toolkit.getDefaultToolkit().beep();
	}
	
	/**
	 * @return The abilities that were not optimized.
	 */
	public AbilityTemplate getUnoptimizableAbilities() {
		return this.unoptimizableAbilities;
	}
}
